package LinkList;

import org.junit.Test;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: LinkList
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-23  22:41
 * @Description: TODO
 * @Version: 1.0
 */
public class 删除链表的倒数第n个结点19 {
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return head;
        }
        int count = 0;
        ListNode new_head = head;
        while (new_head != null) {
            new_head = new_head.next;
            count++;
        }
        ListNode dumpy = new ListNode(-1);
        dumpy.next = head;

        ListNode curr = dumpy;
        // 找到n-1个位置
        for (int i = 1; i < count - n + 1; i++) {
            curr = curr.next;
        }
        curr.next = curr.next.next;
        return dumpy.next;
    }

    // 采用的双指针的方法的来是 是的快指针大于慢指针n 个 然后在到达终点的时候 这个时候就是的满指针的值了

    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;

        ListNode fastIndex = dummyNode;
        ListNode slowIndex = dummyNode;

        // 只要快慢指针相差 n 个结点即可
        for (int i = 0; i < n  ; i++){
            fastIndex = fastIndex.next;
        }

        while (fastIndex.next != null){
            fastIndex = fastIndex.next;
            slowIndex = slowIndex.next;
        }
        //此时 slowIndex 的位置就是待删除元素的前一个位置。
        //具体情况可自己画一个链表长度为 3 的图来模拟代码来理解
        slowIndex.next = slowIndex.next.next;
        return dummyNode.next;
    }

    public ListNode removeNthFromEnd3(ListNode head, int n) {
        ListNode dumpy=new ListNode(-1);
        dumpy.next=head;
        ListNode fast=dumpy;
        while (n>0){
            fast=fast.next;
            n--;
        }
        ListNode slow=dumpy;
        while (fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return dumpy.next;
    }

    @Test
    public void test() {
        ListNode s1 = new ListNode(1);
        ListNode s2 = new ListNode(2);
        ListNode s3 = new ListNode(3);
        ListNode s4 = new ListNode(4);
        ListNode s5 = new ListNode(5);
        s1.next = s2;
        s2.next = s3;
        s3.next = s4;
        s4.next = s5;

        ListNode listNode = removeNthFromEnd(s1, 2);
    }
}
